package 剑指offer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author: tyy 剑指 Offer
 * 260. 只出现一次的数字 III
 * 给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
    进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
    示例 1：
    输入：nums = [1,2,1,3,2,5]
    输出：[3,5]
    解释：[5, 3] 也是有效的答案。
 * @create: 2021-10-21 17:40
 * @description:
 **/
public class Solution12 {
    public int[] singleNumber(int[] nums) {
        /**
         有两个数只出现了一次记为 num1、num2 初始化为 0, 其余的数出现了两次,
         我们可以对所有的数进行一次异或操作, 易知这个结果就等于 num1 和 num2
         的异或结果(相同的数异或结果都为 0, 0和任意数异或结果都为那个数).

         那么我可以考虑异或结果的某个非 0 位如最后一个非 0 位, 因为我们知道只
         有当 num1、num2 在该位不一样的时候才会出现异或结果为 1. 所以我们以该
         位是否为 1 对数组进行划分, 只要该位为 1 就和 num1 异或, 只要该位为 0
         就和 num2 异或, 这样最终得到就是只出现过一次的两个数(其他在该位为 1 或
         0 的数必然出现 0/2 次对异或结果无影响)
         **/
        int num1 = 0, num2 = 0;
        int xor = 0;
        for(int num : nums)
            xor ^= num;

        int bit_1 = 1;
        while((xor & 1) == 0) {
            xor >>= 1;
            bit_1 <<= 1;
        }

        for(int num : nums) {
            if((num & bit_1) == 0)
                num1 ^= num;
            else
                num2 ^= num;
        }

        return new int[]{num1, num2};
    }
    public int[] singleNumber1(int[] nums) {
        List<Integer> list = new ArrayList();
        List<Integer> result = new ArrayList();
        for (int i = 0; i < nums.length; i++) {
            list.add(nums[i]);
        }
        for (int i = 0; i < list.size(); i++) {
            int num = list.get(i);
            list.remove(i);
            int index = list.indexOf(num);
            if (index >= 0) {
                list.remove(index);
                i--;
            }else{
                result.add(num);
            }
            if (i >= 0) {
                i--;
            }

        }
        int answer[] = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            answer[i] = result.get(i);
        }
        return answer;

    }

    public static void main(String[] args) {
        int nums[] = {-1,0,1,2,-1,2};
        int[] integers = new Solution12().singleNumber(nums);

        System.out.println("integers = " + Arrays.toString(integers));
    }
}